package com.lik.javadeep.leetcode;

public class LCS1143 {
    private static class Solution {
        public int longestCommonSubsequence(String text1, String text2) {


            return findLCS(text1, text2);
        }

        private int findLCS(String subText1, String subText2) {
            // 递归基
            if (subText1.length() == 0 || subText2.length() == 0) {
                return 0;
            }

            // 减而治之(最后一个字母相同),规模减小,公共子序列长度+1
            if (subText1.charAt(subText1.length() - 1) == subText2.charAt(subText2.length() - 1)) {
                return 1 + findLCS(subText1.substring(0,subText1.length() - 1),subText2.substring(0,subText2.length() - 1));
            } else {

                // 最后一个字母不同，则出现两个任务，取最大值 (去掉最后一个字母)
                return Math.max(
                        findLCS(subText1.substring(0,subText1.length() - 1),subText2),
                        findLCS(subText1,subText2.substring(0,subText2.length() - 1))
                );
            }
        }
    }

    public static void main(String[] args) {
        int result = new Solution().longestCommonSubsequence("abcde", "ace");

        assert result == 3;
    }

}
